// https://leetcode.cn/problems/remove-duplicate-letters/
// Created by ade on 2022/10/26.
// 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<int> count(26);
        for (auto &i:s) count[i - 'a']++;
        vector<int> st = {};
        vector<int> exist(26);
        for (int i = 0; i < s.size(); i++) {
            int c = s[i] - 'a';
            if (exist[c] == 1) {
                count[c]--;
                continue;
            }
            while (!st.empty() && c < st.back() && count[st.back()] > 0) {
                exist[st.back()] = 0;
                st.pop_back();
            }
            st.push_back(c);
            count[c]--;
            exist[c] = 1;
        }
        string res = "";
        for (int i = 0; i < st.size(); i++) {
            res.push_back(st[i] + 'a');
        }
        return res;
    }
};

int main() {
    Solution so;
    string s = "bbcaac";
    cout << so.removeDuplicateLetters(s);
    return 0;
}
